0099. 恢复二叉搜索树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - Morris 中序遍历

1. 📝 题目描述

• leetcode

给你二叉搜索树的根节点 root，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。

---

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3。交换 2 和 3 使二叉搜索树有效。

---

提示：

• 树上节点的数目在范围 [2, 1000] 内
• -2^31 <= Node.val <= 2^31 - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

2. 🎯 s.1 - Morris 中序遍历

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void recoverTree(struct TreeNode* root) {
    struct TreeNode *first = NULL, *second = NULL, *prev = NULL;
    struct TreeNode* cur = root;
    // Morris 中序遍历
    while (cur) {
        if (cur->left) {
            struct TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur)
                pred = pred->right;
            if (!pred->right) {
                pred->right = cur;
                cur = cur->left;
            } else {
                pred->right = NULL;
                if (prev && prev->val > cur->val) {
                    if (!first)
                        first = prev;
                    second = cur;
                }
                prev = cur;
                cur = cur->right;
            }
        } else {
            if (prev && prev->val > cur->val) {
                if (!first)
                    first = prev;
                second = cur;
            }
            prev = cur;
            cur = cur->right;
        }
    }
    int tmp = first->val;
    first->val = second->val;
    second->val = tmp;
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
  let first = null,
    second = null,
    prev = null
  // Morris 中序遍历
  let cur = root
  while (cur) {
    if (cur.left) {
      let pred = cur.left
      while (pred.right && pred.right !== cur) pred = pred.right
      if (!pred.right) {
        pred.right = cur
        cur = cur.left
      } else {
        pred.right = null
        if (prev && prev.val > cur.val) {
          if (!first) first = prev
          second = cur
        }
        prev = cur
        cur = cur.right
      }
    } else {
      if (prev && prev.val > cur.val) {
        if (!first) first = prev
        second = cur
      }
      prev = cur
      cur = cur.right
    }
  }
  ;[first.val, second.val] = [second.val, first.val]
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        first = second = prev = None
        cur = root
        # Morris 中序遍历
        while cur:
            if cur.left:
                pred = cur.left
                while pred.right and pred.right is not cur:
                    pred = pred.right
                if not pred.right:
                    pred.right = cur
                    cur = cur.left
                else:
                    pred.right = None
                    if prev and prev.val > cur.val:
                        if not first:
                            first = prev
                        second = cur
                    prev = cur
                    cur = cur.right
            else:
                if prev and prev.val > cur.val:
                    if not first:
                        first = prev
                    second = cur
                prev = cur
                cur = cur.right
        first.val, second.val = second.val, first.val

• 时间复杂度：$O(n)$，其中 n 是树的节点数
• 空间复杂度：$O(1)$，Morris 遍历不使用额外栈空间

算法思路：

• BST 的中序遍历是严格递增序列，两个被交换的节点会产生“逆序对”
• 使用 Morris 中序遍历实现 $O(1)$ 空间：找左子树的最右节点（前驱），建立临时线索指向当前节点
• 遍历过程中记录 first、second 两个逆序节点：
  • 第一次发现 prev.val > cur.val 时，first = prev
  • 每次发现逆序时，second = cur
• 最后交换 first 和 second 的值即可恢复 BST